package Example_practice02;

import java.security.acl.AclNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Mypoint{
    double x;
    double y;
    public Mypoint(double x,double y){
        this.x=x;
        this.y=y;
    }
    //计算两点之间的距离
    public double getDistance(Mypoint Another_point){
        double dx=x-Another_point.x;
        double dy=y-Another_point.y;
        return Math.sqrt(dx*dx+dy*dy);
    }
}
public class DCClosest {
    //分治法求最接近点对
    public static double closestPair(Mypoint[] mypoints,int start,int end){
        //如果只有一个点或者没有，返回正无穷
        if (start==end){
            return Double.POSITIVE_INFINITY;
        }
        //如果只有两个点，直接计算
        else if (end- start==1){
            return mypoints[end].getDistance(mypoints[start]);
        }
        //否则递归地进行分治计算
        else {
            //按横坐标从小到大排列点对数组
            Arrays.sort(mypoints,(o1,o2)->Double.compare(o1.x,o2.x));
            int mid=(start+end)/2;
            double leftDistance= closestPair(mypoints,start,mid);
            double rightDistance= closestPair(mypoints,mid+1,end);

            //比较左边和右边，取较小值
            double minDistance=Math.min(leftDistance,rightDistance);

            //还得考虑中间区域的情况
            double midDistance=findCrossRegion(mypoints,start,end,mid,minDistance);
            minDistance=Math.min(midDistance,minDistance);
            return minDistance;
        }
    }
    private static double findCrossRegion(Mypoint[] mypoints,int start,int end,int mid,double minDistance){
        List<Mypoint> midRegion=new ArrayList<>();
        //将中间区域的点加入列表
        for (int i=start;i<end;i++){
            if (Math.abs(mypoints[i].x-mypoints[mid].x)<minDistance){
                midRegion.add(mypoints[i]);
            }
        }
        //根据Y坐标对中间区域的点按从小到大排序
        Collections.sort(midRegion,(p1,p2)->Double.compare(p1.y,p2.y));

        int size=midRegion.size();
        //寻找最接近的点
        for (int i=0;i<size-1;i++){
            for (int j=i+1;j<size && midRegion.get(j).y-midRegion.get(i).y<minDistance;j++){
                double curDistance=midRegion.get(i).getDistance(midRegion.get(j));
                if (curDistance<minDistance){
                    minDistance=curDistance;
                }
            }
        }
        return minDistance;
    }
}
